{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #全排列 II "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: permuteUnique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #全排列 II "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个可包含重复数字的整数集合&nbsp;<code>nums</code> ，<strong>按任意顺序</strong> 返回它所有不重复的全排列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,2]\n",
    "<strong>输出：</strong>\n",
    "[[1,1,2],\n",
    " [1,2,1],\n",
    " [2,1,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 8</code></li>\n",
    "\t<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 47&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/permutations-ii/\">https://leetcode-cn.com/problems/permutations-ii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [7p8L0Z](https://leetcode.cn/problems/7p8L0Z/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [7p8L0Z](https://leetcode.cn/problems/7p8L0Z/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for x in itertools.permutations(nums,len(nums)):\n",
    "            sublist = list(x)\n",
    "            if sublist not in res:\n",
    "                res.append(sublist)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrack(seen, path):\n",
    "            if len(path) == len(nums):\n",
    "                if ''.join(path) not in path_set:\n",
    "                    path_set.add(''.join(path))\n",
    "                    ans.append([int(x) for x in path])\n",
    "                return\n",
    "            \n",
    "            for i in range(len(nums)):\n",
    "                if not seen[i]:\n",
    "                    seen[i] = True\n",
    "                    path.append(str(nums[i]))\n",
    "                    backtrack(seen, path)\n",
    "                    seen[i] = False\n",
    "                    path.pop()\n",
    "\n",
    "        ans = []\n",
    "        path_set = set()\n",
    "        backtrack([False]*len(nums), [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        flag = set()\n",
    "        result = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        def backtrack(array,n):\n",
    "            if len(path) == n:\n",
    "                tp = tuple(path)\n",
    "                if tp not in flag:\n",
    "                    result.append(path[:])\n",
    "                    flag.add(tuple(path))\n",
    "                return\n",
    "            for idx,val in enumerate(array):\n",
    "                path.append(val)\n",
    "                del array[idx]\n",
    "                backtrack(array, n)\n",
    "                array.insert(idx,val)\n",
    "                path.pop()\n",
    "        backtrack(nums, n)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for x in itertools.permutations(nums):\n",
    "            sublist = list(x)\n",
    "            if sublist not in res:\n",
    "                res.append(sublist)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(x):\n",
    "            if x == length_nums:\n",
    "                temp_string = ''.join([str(x) for x in temp])\n",
    "                if temp_string not in dic:\n",
    "                    ans.append(list(temp))\n",
    "                    dic[temp_string] = 1\n",
    "            else:\n",
    "                for i in range(length_nums):\n",
    "                    if label[i] == False:\n",
    "                        label[i] = True\n",
    "                        temp[x] = nums[i]\n",
    "                        dfs(x + 1)\n",
    "                        label[i] = False\n",
    "        \n",
    "        ans = []\n",
    "        dic = {}\n",
    "        length_nums = len(nums)\n",
    "        temp = [0] * length_nums\n",
    "        label = [False] * length_nums\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        has=set()\n",
    "        nums.sort()\n",
    "        def go(ind):\n",
    "            if ind==len(nums):\n",
    "                k=tuple(nums)\n",
    "                if k in has:\n",
    "                    return\n",
    "                has.add(k)\n",
    "                \n",
    "                ans.append(nums[:])\n",
    "                return\n",
    "            for i in range(ind,len(nums)):\n",
    "                nums[i],nums[ind]=nums[ind],nums[i]\n",
    "                go(ind+1)\n",
    "                nums[i],nums[ind]=nums[ind],nums[i]\n",
    "        go(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        '''原来第一次做出来的'''\n",
    "        # def dfs(q):\n",
    "        #     if len(q) == len(nums) and tuple(q) not in st:\n",
    "        #         st.add(tuple(q))\n",
    "        #         res.append(q[:])\n",
    "        #         return # ！要return\n",
    "        #     for i in range(len(nums)):\n",
    "        #         if vis[i] == 0:\n",
    "        #             vis[i] = 1\n",
    "        #             q.append(nums[i])\n",
    "        #             dfs(q)\n",
    "        #             q.pop()\n",
    "        #             vis[i] = 0\n",
    "        \n",
    "        # res = []\n",
    "        # st = set()\n",
    "        # vis = [0 for _ in range(len(nums))]\n",
    "        # dfs([])\n",
    "        # return res\n",
    "        '''第二遍第一次尝试，没做出来'''\n",
    "        def dfs(q):\n",
    "            if len(q) == len(nums) and tuple(q) not in st:\n",
    "            #if len(q) == len(nums):\n",
    "                res.append(q[:])\n",
    "                st.add(tuple(q[:]))\n",
    "                return\n",
    "            \n",
    "            #for i in range(pos, len(nums)):\n",
    "            for i in range(len(nums)):\n",
    "                #if nums[i] not in vis:\n",
    "                if vis[i] == 0:\n",
    "                    q.append(nums[i])\n",
    "                    #print(q)\n",
    "                    #vis.add(nums[i])\n",
    "                    vis[i] = 1\n",
    "                    dfs(q)\n",
    "                    q.pop()\n",
    "                    #vis.remove(nums[i])\n",
    "                    vis[i] = 0\n",
    "        \n",
    "        res = []\n",
    "        #nums.sort()\n",
    "        #vis = set()\n",
    "        vis = [0]*len(nums)\n",
    "        st = set()\n",
    "        \n",
    "        dfs([])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def helper(index,result,dic):\n",
    "            if index == len(nums):\n",
    "                if nums not in result:\n",
    "                    result.append(copy.deepcopy(nums))\n",
    "            else:\n",
    "                for i in range(index,len(nums)):\n",
    "                    dic.append(nums[i])\n",
    "                    nums[index],nums[i] = nums[i],nums[index]\n",
    "                    helper(index+1,result,dic)\n",
    "                    nums[index],nums[i] = nums[i],nums[index]\n",
    "        result = []\n",
    "        helper(0,result,[])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        path, result = [], []\n",
    "        self.permute_inner(sorted(nums), path, result)\n",
    "        return result\n",
    "    \n",
    "    def permute_inner(self, nums: List[int], path:List[int], result:List[List[int]]):\n",
    "        if len(nums) == 0:\n",
    "            result.append(path[:])\n",
    "            return\n",
    "        prev = float('inf')\n",
    "        for i in range(len(nums)):\n",
    "            if prev != nums[i]:\n",
    "                path.append(nums[i])\n",
    "                self.permute_inner(nums[0:i] + nums[i + 1:], path, result)\n",
    "                path.pop()\n",
    "            prev = nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        li, res = [], []\n",
    "        seen = set()\n",
    "        def dfs(pos):\n",
    "            if pos==n:\n",
    "                x = tuple(li)\n",
    "                if  x not in seen:\n",
    "                    seen.add(x)\n",
    "                    res.append(li[:])\n",
    "                return\n",
    "            for i in range(pos,n):\n",
    "                \n",
    "                nums[pos],nums[i] = nums[i],nums[pos]\n",
    "                li.append(nums[pos])\n",
    "                dfs(pos+1)\n",
    "                li.pop()\n",
    "                nums[pos], nums[i] = nums[i],nums[pos]\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtracking(path, res, used):\n",
    "            if len(path) == len(nums):\n",
    "                if path[:] not in res:\n",
    "                    res.append(path[:])\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if used[i] == 0 and( i==0 or used[i-1] == 1 or nums[i] != nums[i-1]):\n",
    "                    used[i] = 1\n",
    "                    path.append(nums[i])\n",
    "                    backtracking(path, res, used)\n",
    "                    path.pop()\n",
    "                    used[i] = 0\n",
    "        res = []\n",
    "        path = []\n",
    "        nums.sort()\n",
    "        used = [0 for i in range(len(nums))]\n",
    "        backtracking(path, res, used)\n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "        self.n = len(nums)\n",
    "        nums.sort()\n",
    "        self.used = [False] * self.n\n",
    "        self.backtrack(nums)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, nums):\n",
    "        if len(self.track) == len(nums):\n",
    "            self.res.append(self.track[:])\n",
    "            return\n",
    "        \n",
    "        \n",
    "        for i in range(0, self.n):\n",
    "            if self.used[i]:\n",
    "                continue\n",
    "\n",
    "            if i > 0 and nums[i] == nums[i-1] and not self.used[i-1]:\n",
    "                continue\n",
    "\n",
    "            self.track.append(nums[i])\n",
    "            self.used[i] = True\n",
    "\n",
    "            self.backtrack(nums)\n",
    "\n",
    "            self.track.pop()\n",
    "            self.used[i] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        candidates = collections.deque(nums)\n",
    "        self.length = len(nums)\n",
    "        self.result = []\n",
    "        self.re = set()\n",
    "        def permutation(temp, l, candidate):\n",
    "            if self.length != l:\n",
    "                for _ in range(self.length-l):\n",
    "                    temp.append(candidate.popleft())\n",
    "                    permutation(temp, l+1, candidate)\n",
    "                    candidate.append(temp.pop())\n",
    "            else:\n",
    "                r = temp.copy()\n",
    "                t = tuple(r)\n",
    "                if t in self.re:\n",
    "                    return\n",
    "                self.result.append(r)\n",
    "                self.re.add(t)\n",
    "            return\n",
    "\n",
    "        permutation([], 0, candidates)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums:\n",
    "            return []\n",
    "   \n",
    "        def get_ans(seen, ans):\n",
    "            if len(ans) == len(nums):\n",
    "                if ans not in res:\n",
    "                    res.append(ans)\n",
    "                return\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                if i not in seen:\n",
    "                    get_ans(seen+[i], ans+[nums[i]])\n",
    "                \n",
    "\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            ans = []\n",
    "            seen = []\n",
    "            get_ans(seen+[i], ans+[nums[i]])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        self.backtracking(res, [], nums, [0] * len(nums))\n",
    "        return res\n",
    "    \n",
    "    def backtracking(self, res, path, nums, used):\n",
    "        if len(path) == len(nums):\n",
    "            res.append(path[:])\n",
    "            return \n",
    "        for i in range(len(nums)):\n",
    "            if i != 0 and nums[i] == nums[i - 1] and not used[i - 1]:\n",
    "                continue\n",
    "            if not used[i]:\n",
    "                path.append(nums[i])\n",
    "                used[i] = 1\n",
    "                self.backtracking(res, path, nums, used)\n",
    "                used[i] = 0\n",
    "                path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(nums, used, path, res):\n",
    "            # 终止条件\n",
    "            # 避免重复: 相当于生成之后才进行判断，可以在 path 阶段就判断，降低复杂度， 见方法二\n",
    "            if len(path[:]) == len(nums) and path[:] not in res:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            # 循环\n",
    "            for i in range(len(nums)):\n",
    "                if not used[i]:\n",
    "                    used[i] = True\n",
    "                    path.append(nums[i])\n",
    "                    dfs(nums, used, path, res)\n",
    "                    used[i] = False\n",
    "                    path.pop()\n",
    "            \n",
    "        res = []\n",
    "        used = [False for _ in range(len(nums))]\n",
    "        dfs(nums, used, [], res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def tracingback(tmp, flags, nums, ans):\n",
    "    if len(tmp) == len(nums):\n",
    "        ans.append(tmp[:])\n",
    "    else:\n",
    "        # print(tmp)\n",
    "        # print(flags)\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0 and nums[i] == nums[i-1] and flags[i-1]:\n",
    "                continue\n",
    "            if flags[i]:\n",
    "                tmp.append(nums[i])\n",
    "                flags[i] = 0\n",
    "                tracingback(tmp, flags, nums, ans)\n",
    "                tmp.pop()\n",
    "                flags[i] = 1 \n",
    "\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        tracingback([], [1] * len(nums), nums, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/hui-su-sua-56e11\n",
    "# 回溯算法\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort() # 因为要去重，所以排序。排序后方便去重\n",
    "        track = [] # 路径\n",
    "        used = [False] * len(nums) # 因为要返回不重复的index的数据，所以用used来记录哪些用过。相当于选择列表\n",
    "        self.backtrack(nums, track, used) # 传入路径、选择列表\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, nums, track, used):\n",
    "        # 终止条件\n",
    "        if len(track) == len(nums):\n",
    "            self.res.append(track[:]) # 之所以写[:]，跟写.copy()是一个意思，就那种储存还没改变那种东西\n",
    "            return\n",
    "        \n",
    "        # 选择列表\n",
    "        for i in range(len(nums)):\n",
    "            # if nums[i] in track: # 这种写法在这里失效了。因为nums是有重复元素的。如果nums没有重复元素，这样写是可以的\n",
    "            #     continue\n",
    "\n",
    "            if used[i]:\n",
    "                continue\n",
    "            # 剪枝\n",
    "            if i > 0 and nums[i] == nums[i-1] and not used[i-1]: # 理解为上一步有撤回，撤回就相当于false了嘛\n",
    "                continue\n",
    "\n",
    "            # 做选择\n",
    "            track.append(nums[i])\n",
    "            used[i] = True\n",
    "            # 回溯\n",
    "            self.backtrack(nums, track, used)\n",
    "            # 撤回选择\n",
    "            track.pop()\n",
    "            used[i] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         self.res = []\n",
    "\n",
    "#     def permuteUnique(self, nums):\n",
    "#         track = []\n",
    "#         used = [False] * len(nums)\n",
    "#         self.backtrack(track,nums)\n",
    "#         # import pdb;pdb.set_trace()\n",
    "#         res_final = []\n",
    "#         for i in self.res:\n",
    "#             if i not in res_final:\n",
    "#                 res_final.append(i)\n",
    "#         return res_final\n",
    "\n",
    "    \n",
    "#     def backtrack(self, track, nums):\n",
    "#         if not len(nums):\n",
    "#             self.res.append(track[:])\n",
    "#             return\n",
    "        \n",
    "#         for i in range(len(nums)):\n",
    "            \n",
    "#             track.append(nums[i])\n",
    "#             self.backtrack(track, nums[:i]+nums[i+1:])\n",
    "#             track.pop()\n",
    "\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         self.res = []\n",
    "\n",
    "#     def permuteUnique(self, nums):\n",
    "#         track = []\n",
    "#         nums.sort()\n",
    "#         used = [False] * len(nums)\n",
    "#         self.backtrack(nums,track,used)\n",
    "#         return self.res\n",
    "\n",
    "#     def backtrack(self,nums, track, used):\n",
    "#         if len(track) == len(nums):\n",
    "#             self.res.append(track[:])\n",
    "        \n",
    "#         for i in range(len(nums)):\n",
    "#             if used[i]:\n",
    "#                 continue\n",
    "#             if i>0 and nums[i] == nums[i-1] and not used[i-1]:\n",
    "#                 continue\n",
    "            \n",
    "#             used[i] = True\n",
    "#             track.append(nums[i])\n",
    "#             self.backtrack(nums,track,used)\n",
    "#             used[i] = False\n",
    "#             track.pop()\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def permuteUnique(self, nums):\n",
    "        track = []\n",
    "        used = [False] * len(nums)\n",
    "        nums.sort()\n",
    "        self.backtrack(nums,track,used)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self,nums,track,used):\n",
    "        if len(track) == len(nums):\n",
    "            self.res.append(track[:])\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            if i>0 and used[i-1] == False and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            track.append(nums[i])\n",
    "            used[i] = True\n",
    "            self.backtrack(nums,track,used)\n",
    "            used[i] = False\n",
    "            track.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        list1 = []\n",
    "\n",
    "        t1 = itertools.permutations(nums, len(nums))\n",
    "        for i in t1:\n",
    "            if list(i) not in list1:\n",
    "                list1.append(list(i))\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums):\n",
    "        nums.sort()  # 排序\n",
    "        result = []\n",
    "        self.backtracking(nums, [], [False] * len(nums), result)\n",
    "        return result\n",
    "\n",
    "    def backtracking(self, nums, path, used, result):\n",
    "        if len(path) == len(nums):\n",
    "            result.append(path[:])\n",
    "            return\n",
    "        for i in range(len(nums)):\n",
    "            if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:\n",
    "                continue\n",
    "            used[i] = True\n",
    "            path.append(nums[i])\n",
    "            self.backtracking(nums, path, used, result)\n",
    "            path.pop()\n",
    "            used[i] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        stack,ans,res = [],[],[]\n",
    "        def track(i,stack,ans,res):\n",
    "            if i == n:\n",
    "                if ans not in res:\n",
    "                    res.append(ans[:])\n",
    "                return \n",
    "            \n",
    "            for inx in range(n):\n",
    "                if inx not in stack:\n",
    "                    stack.append(inx)\n",
    "                    ans.append(nums[inx])\n",
    "                    track(i+1,stack,ans,res)\n",
    "                    stack.pop()\n",
    "                    ans.pop()\n",
    "            \n",
    "        track(0,stack,ans,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtrack(self, nums, used, path, res):\n",
    "        if len(path) == len(nums):\n",
    "            res.append(path.copy())\n",
    "            return \n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            if i > 0 and nums[i] == nums[i-1] and (not used[i - 1]):\n",
    "                continue\n",
    "            \n",
    "            used[i] = True\n",
    "            path.append(nums[i])\n",
    "            self.backtrack(nums, used, path, res)\n",
    "            used[i] = False\n",
    "            path.pop()\n",
    "\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        used = [False] * len(nums)\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        self.backtrack(nums, used, [], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res=[]\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        path=[]\n",
    "        used=[False]*len(nums)\n",
    "        nums.sort()\n",
    "        self.trace(nums,path,used)\n",
    "        return self.res\n",
    "    def trace(self,nums,path,used):\n",
    "        if len(path)==len(nums):\n",
    "            self.res.append(path.copy())\n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            if i>0 and nums[i]==nums[i-1] and not used[i-1]:\n",
    "                continue\n",
    "            path.append(nums[i])\n",
    "            used[i]=True\n",
    "            self.trace(nums,path,used)\n",
    "            path.pop()\n",
    "            used[i]=False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        rs = [[nums[0]]]\n",
    "        if len(nums) == 1:\n",
    "            return rs\n",
    "        \n",
    "        index = 1\n",
    "        while index != len(nums):\n",
    "            nextNum = nums[index]\n",
    "            index += 1\n",
    "            \n",
    "            numberOfRead = len(rs)\n",
    "            while numberOfRead > 0:\n",
    "                item = rs.pop(0)\n",
    "                locationToInsert = len(item) + 1\n",
    "                for i in range(locationToInsert):\n",
    "                    \n",
    "                    newItem = item[:i] + [nextNum] + item[i:]\n",
    "                    if newItem not in rs:\n",
    "                        rs.append(newItem)\n",
    "                numberOfRead -= 1\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        return self.permute_impl(nums, len(nums), [False] * len(nums), [])\n",
    "\n",
    "    def permute_impl(\n",
    "        self,\n",
    "        nums: List[int],\n",
    "        left: int,\n",
    "        used: List[bool],\n",
    "        permutation: List[int],\n",
    "    ) -> List[List[int]]:\n",
    "        permutations = []\n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:\n",
    "                continue\n",
    "            used[i] = True\n",
    "            left -= 1\n",
    "            if left == 0:\n",
    "                permutations.append(permutation + [nums[i]])\n",
    "            else:\n",
    "                permutations += self.permute_impl(\n",
    "                    nums,\n",
    "                    left,\n",
    "                    used,\n",
    "                    permutation + [nums[i]],\n",
    "                )\n",
    "            used[i] = False\n",
    "            left += 1\n",
    "        return permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.results = []\n",
    "\n",
    "\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        self.traverslbacking(nums,len(nums))\n",
    "        return self.results\n",
    "    \n",
    "    \n",
    "    def traverslbacking(self,nums,lenth):\n",
    "        if len(self.path) == lenth:\n",
    "            self.results.append(self.path[:])\n",
    "        if  len(nums) == 0:\n",
    "            return None\n",
    "        chongfu_set = set()\n",
    "        for index in range(len(nums)):\n",
    "            if nums[index] not in chongfu_set:\n",
    "                chongfu_set.add(nums[index])\n",
    "                self.path.append(nums[index])\n",
    "                self.traverslbacking(nums[0:index]+nums[index+1:],lenth)\n",
    "                self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        used=[False]*len(nums)\n",
    "        res=[]\n",
    "        self.dfs(nums,[],res,used)\n",
    "        return res\n",
    "\n",
    "        \n",
    "    def dfs(self,nums,pain,res,used):\n",
    "        if len(pain)==len(nums):\n",
    "            res.append(pain)\n",
    "            return\n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            if i>0 and nums[i]==nums[i-1] and not used[i-1]:\n",
    "                continue\n",
    "            used[i]=True\n",
    "            self.dfs(nums,pain+[nums[i]],res,used)\n",
    "            used[i]=False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        path=[]\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        tag=[False]*n\n",
    "\n",
    "        def backtrack(u):\n",
    "            if u>=n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(n):\n",
    "                if i!=0 and nums[i]==nums[i-1] and not tag[i-1]:\n",
    "                    continue\n",
    "\n",
    "                if not tag[i]:\n",
    "                    tag[i]=True\n",
    "                    path.append(nums[i])\n",
    "                    backtrack(u+1)\n",
    "                    tag[i]=False\n",
    "                    path.pop()\n",
    "        \n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = self.func1(nums,[],[])\n",
    "        return res\n",
    "\n",
    "\n",
    "    def func1(self,nums,arr,res):\n",
    "        if not nums:\n",
    "            res.append(arr)\n",
    "            return res\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if i==0 or nums[i]!=nums[i-1]:\n",
    "                nums_new = nums[0:i]+nums[i+1:]\n",
    "                arr.append(nums[i])\n",
    "                self.func1(nums_new,arr[:],res)\n",
    "                arr.pop()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        rs = [[nums[0]]]\n",
    "        if len(nums) == 1:\n",
    "            return rs\n",
    "        \n",
    "        index = 1\n",
    "        while index != len(nums):\n",
    "            nextNum = nums[index]\n",
    "            index += 1\n",
    "            \n",
    "            numberOfRead = len(rs)\n",
    "            while numberOfRead > 0:\n",
    "                item = rs.pop(0)\n",
    "                locationToInsert = len(item) + 1\n",
    "                for i in range(locationToInsert):\n",
    "                    \n",
    "                    newItem = item[:i] + [nextNum] + item[i:]\n",
    "                    if newItem not in rs:\n",
    "                        rs.append(newItem)\n",
    "                numberOfRead -= 1\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for x in itertools.permutations(nums,len(nums)):\n",
    "            sublist = list(x)\n",
    "            if sublist not in res:\n",
    "                res.append(sublist)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "       \n",
    "        def backtrack(first = 0):\n",
    "            # if the first integer to consider has one beyond the last index\n",
    "            if first == n:\n",
    "                output.append(nums[:])\n",
    "                return\n",
    "            # permutation made by swapping elements i and first for the rest of the array\n",
    "            for i in range(first, n):\n",
    "                # deduplicate\n",
    "                if nums[i] in nums[first:i]:\n",
    "                    continue\n",
    "                nums[first], nums[i] = nums[i], nums[first]\n",
    "                # use next integers to complete the permutations\n",
    "                backtrack(first + 1)\n",
    "                # backtrack\n",
    "                nums[first], nums[i] = nums[i], nums[first]\n",
    "\n",
    "        n = len(nums)\n",
    "        output = []\n",
    "        backtrack()\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        s = set()\n",
    "        for p in itertools.permutations(nums):\n",
    "            s.add(p)\n",
    "        return list(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrack(index):\n",
    "            if index == len(nums):\n",
    "                result.append(list(nums))\n",
    "                return\n",
    "            visited = set()\n",
    "            for i in range(index,len(nums)):\n",
    "                if nums[i] not in visited:\n",
    "                    visited.add(nums[i])\n",
    "                    nums[i],nums[index] = nums[index],nums[i]\n",
    "                    backtrack(index+1)\n",
    "                    nums[i],nums[index] = nums[index],nums[i]\n",
    "        result = []\n",
    "        backtrack(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def process(self, k):\n",
    "        if k >= self.length:\n",
    "            self.result.append(self.tmp[:])\n",
    "            return\n",
    "\n",
    "        for i in range(self.length):\n",
    "            if self.used[i]:\n",
    "                continue\n",
    "            if i>0 and (self.nums[i] == self.nums[i-1]) and (not self.used[i-1]):\n",
    "                continue\n",
    "            self.used[i] = True\n",
    "            self.tmp.append(self.nums[i])\n",
    "            self.process(k+1)\n",
    "            self.used[i] = False\n",
    "            self.tmp.pop()\n",
    "\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.length = len(nums)\n",
    "        self.nums = nums\n",
    "        self.nums.sort()\n",
    "        self.tmp = []\n",
    "        self.result = []\n",
    "        self.used = []\n",
    "        \n",
    "        for i in range(self.length):\n",
    "            self.used.append(False)\n",
    "\n",
    "        self.process(0)\n",
    "\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def f(i,nums,ans):\n",
    "            if i==len(nums):\n",
    "                ans.append(nums.copy())\n",
    "            else:\n",
    "                visit = set()\n",
    "                for j in range(i,len(nums)):\n",
    "                    if nums[j] not in visit:\n",
    "                        visit.add(nums[j])\n",
    "                        nums[i],nums[j] = nums[j],nums[i]\n",
    "                        f(i+1,nums,ans)\n",
    "                        nums[i],nums[j] = nums[j],nums[i]\n",
    "        ans = []\n",
    "        f(0,nums,ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        self.process(nums, 0, res)\n",
    "        return res\n",
    "\n",
    "    def process(self, nums: List, i, res: List):\n",
    "        if i == len(nums):\n",
    "            # 添加结果时记得拷贝\n",
    "            res.append(copy.deepcopy(nums))\n",
    "            return None\n",
    "        \n",
    "        # 用于去重\n",
    "        existed = set()\n",
    "        for j in range(i, len(nums)):\n",
    "            if nums[j] not in existed:\n",
    "                existed.add(nums[j])\n",
    "                self.swap(nums, i, j)\n",
    "                self.process(nums, i+1, res)\n",
    "                self.swap(nums, j, i)\n",
    "    \n",
    "    def swap(self, lst, i, j):\n",
    "        lst[i], lst[j] = lst[j], lst[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def dfs(cur_nums, remain_nums):\n",
    "            if not remain_nums:\n",
    "                res.append(cur_nums)\n",
    "            \n",
    "            seen = set()\n",
    "            for i, num in enumerate(remain_nums):\n",
    "                if num in seen:\n",
    "                    continue\n",
    "                seen.add(num)\n",
    "                dfs(cur_nums + [num], remain_nums[:i] + remain_nums[i+1:])\n",
    "        \n",
    "        dfs([], nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        h = Counter(nums)\n",
    "        n = len(nums)\n",
    "        k = list(h.keys())\n",
    "        ans = []\n",
    "\n",
    "        def dsf(t, p):\n",
    "            nonlocal ans\n",
    "            if len(t) == n:\n",
    "                ans.append(t)\n",
    "                return\n",
    "            for v in k:\n",
    "                if v == p or not h[v]:\n",
    "                    continue\n",
    "                for c in range(1, h[v] + 1):\n",
    "                    h[v] -= c\n",
    "                    dsf(t + [v] * c, v)\n",
    "                    h[v] += c\n",
    "            return\n",
    "        \n",
    "        dsf([], None)\n",
    "        return ans\n",
    "            \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        path = [0] * n\n",
    "        used = [False] * n\n",
    "        nums.sort()\n",
    "\n",
    "        def dfs(u):\n",
    "            if u == n:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):\n",
    "                    continue\n",
    "                path[u] = nums[i]\n",
    "                used[i] = True\n",
    "                dfs(u + 1)\n",
    "                used[i] = False\n",
    "\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        used = [0] * n\n",
    "        path = []\n",
    "        res = []\n",
    "        def dfs(depth):\n",
    "            if depth == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if not used[i]:\n",
    "                    if i and nums[i] == nums[i-1] and not used[i-1]:\n",
    "                        continue\n",
    "                    path.append(nums[i])\n",
    "                    used[i] = 1\n",
    "                    dfs(depth+1)\n",
    "                    path.pop()\n",
    "                    used[i] = 0\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        used = [0] * n\n",
    "\n",
    "        ans = []\n",
    "        def backtrack(path, used):\n",
    "            if sum(used)==n:\n",
    "                ans.append(path+[])\n",
    "                return\n",
    "            \n",
    "            for i in range(0, n):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                \n",
    "                if i>0 and nums[i]==nums[i-1] and used[i-1]==0:\n",
    "                    continue\n",
    "\n",
    "                used[i] = 1\n",
    "                path.append(nums[i])\n",
    "                backtrack(path, used)\n",
    "                used[i] = 0\n",
    "                path.pop()\n",
    "        \n",
    "        backtrack([], used)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(set(permutations(nums,len(nums))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        path=[]\n",
    "        visited=[False for _ in range(n)]\n",
    "        def backtrace(depth=0):\n",
    "            if depth==n:\n",
    "                res.append(path[:])\n",
    "            for i in range(0,n):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                if i>0 and nums[i]==nums[i-1] and not visited[i-1]:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                visited[i]=True\n",
    "                backtrace(depth+1)\n",
    "                visited[i]=False\n",
    "                path.pop()\n",
    "        backtrace()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        used = [False]*n\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                if path not in res:\n",
    "                    res.append(path.copy())\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if used[j] == False:\n",
    "                    used[j] = True\n",
    "                    path.append(nums[j])\n",
    "                    dfs(i+1)\n",
    "                    used[j] = False\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res, path, path_index = [], [], []\n",
    "        nums.sort()\n",
    "        nums_index = [i for i in range(len(nums))]\n",
    "\n",
    "        def dfs(idx, path_index, path):\n",
    "            if len(path) == len(nums_index):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "\n",
    "            for i in range(len(nums_index)):\n",
    "                if nums_index[i] in path_index:\n",
    "                    continue\n",
    "                if i>=1 and nums[i-1] == nums[i] and i-1 in path_index:\n",
    "                    continue\n",
    "\n",
    "                path_index.append(nums_index[i])\n",
    "                path.append(nums[i])\n",
    "\n",
    "\n",
    "                dfs(0, path_index, path)\n",
    "                path_index.pop()\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0, path_index, path)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        def dfs(x):\n",
    "            if x == n - 1:\n",
    "                res.append(list(nums))\n",
    "                return\n",
    "            st = set()\n",
    "            for i in range(x, n):\n",
    "                if nums[i] in st: continue\n",
    "                st.add(nums[i])\n",
    "                nums[i], nums[x] = nums[x], nums[i]\n",
    "                dfs(x + 1)\n",
    "                nums[i], nums[x] = nums[x], nums[i]\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        self.used = [False] * len(nums)    \n",
    "        self.backtrack(nums)\n",
    "        return self.res\n",
    "    \n",
    "    def backtrack(self, nums: List[int]):\n",
    "        # base case  触发结束条件\n",
    "        if len(self.track) == len(nums):\n",
    "            self.res.append(self.track.copy())\n",
    "            return\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if self.used[i]: \n",
    "                continue\n",
    "            if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]:\n",
    "                continue\n",
    "                \n",
    "            self.track.append(nums[i])\n",
    "            self.used[i] = True\n",
    "            self.backtrack(nums)\n",
    "            self.track.pop()\n",
    "            self.used[i] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        path = []\n",
    "        visited = [False] * n\n",
    "        def backtrack(idx : int) -> None:\n",
    "            if idx == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range (0, n):\n",
    "                if visited[i] == True:\n",
    "                    continue\n",
    "                if 0 < i and nums[i - 1] == nums[i] and visited[i - 1] == False:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                visited[i] = True\n",
    "                backtrack(idx + 1)\n",
    "                visited[i] = False\n",
    "                path.pop()\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(nums, path, used):\n",
    "            if len(path)==len(nums):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(len(nums)):\n",
    "                if not used[i]:\n",
    "                    if i>0 and nums[i]==nums[i-1] and not used[i-1]:\n",
    "                        continue\n",
    "                    path.append(nums[i])\n",
    "                    used[i]=True\n",
    "                    dfs(nums, path, used)\n",
    "                    path.pop()\n",
    "                    used[i]=False\n",
    "        \n",
    "        res = []\n",
    "        nums.sort()\n",
    "        dfs(nums, [], [False]*len(nums))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self,nums:List[int])-> List[List[int]]:\n",
    "        numsLen = len(nums)\n",
    "        target = -2147483647\n",
    "        part = [target]*numsLen\n",
    "        res = []\n",
    "        def combine(n,partRes):\n",
    "            nonlocal numsLen,res,target,nums \n",
    "            if n == numsLen:\n",
    "                if partRes not in res:\n",
    "                    res.append(partRes)\n",
    "                return\n",
    "            num = nums[n]\n",
    "            for i in range(numsLen):\n",
    "                if partRes[i]==target:\n",
    "                    finalRes = partRes.copy()\n",
    "                    finalRes[i] = num\n",
    "                    combine(n+1,finalRes)\n",
    "        combine(0,part)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        vis = [False for _ in nums]\n",
    "        nums.sort()\n",
    "        self.res = []\n",
    "        path = []\n",
    "        def dfs():\n",
    "            if len(path) == len(nums):\n",
    "                self.res.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(len(nums)):\n",
    "                if (i > 0 and nums[i] == nums[i - 1] and not vis[i - 1]) or vis[i] == True:\n",
    "                    continue\n",
    "       \n",
    "                path.append(nums[i])\n",
    "                vis[i] = True\n",
    "                dfs()\n",
    "                vis[i] = False\n",
    "                path.pop()\n",
    "        dfs()\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        n = len(nums)\n",
    "        used = [0]*n\n",
    "        nums.sort()\n",
    "        res = []\n",
    "\n",
    "        def backtrack(nums, path):\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if used[i] == 1:\n",
    "                    continue\n",
    "                if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0:\n",
    "                    continue\n",
    "                used[i] = 1\n",
    "                path.append(nums[i])\n",
    "                backtrack(nums, path)\n",
    "                path.pop()\n",
    "                used[i] = 0\n",
    "        \n",
    "        backtrack(nums, [])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans=list()\n",
    "        def dfs(index):\n",
    "            if index==len(nums):\n",
    "                tmp=nums[:]\n",
    "                if tmp not in ans:\n",
    "                    ans.append(nums[:])\n",
    "                return\n",
    "\n",
    "            for j in range(index,len(nums)):\n",
    "                if nums[j]!=nums[index]:\n",
    "                    nums[j],nums[index]=nums[index],nums[j]\n",
    "                    dfs(index+1)\n",
    "                    nums[j],nums[index]=nums[index],nums[j]\n",
    "                else:\n",
    "                    dfs(index+1)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        def dfs(path,nums,used):\n",
    "            if path in res:\n",
    "                return\n",
    "            if len(path)==len(nums):\n",
    "                res.append(path[:])\n",
    "            for i in range(len(nums)):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                used[i]=True\n",
    "                path.append(nums[i])\n",
    "                dfs(path,nums,used)\n",
    "                path.pop()\n",
    "                used[i]=False\n",
    "        used=[False for _ in range(len(nums))]\n",
    "        dfs([],nums,used)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(used, n, path):\n",
    "            if len(path) == n:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if (i>0 and nums[i]==nums[i-1] and not used[i-1]) or used[i]:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = True\n",
    "                dfs(used,n,path)\n",
    "                used[i] = False\n",
    "                path.pop()\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        dfs([False]*n, n, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        path = []\n",
    "        ans =[]\n",
    "        n =len(nums)\n",
    "        nums.sort()\n",
    "        has_used =[0]*n\n",
    "\n",
    "        def dfs(i):\n",
    "            print(path)\n",
    "            if i == n and path not in ans:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "\n",
    "            for j in range(0,n):\n",
    "                if j>1 and nums[j] == nums[j-1] and has_used[j-1]==1:\n",
    "                    continue\n",
    "                if has_used[j] == 0:\n",
    "                    has_used[j]=1\n",
    "                    path.append(nums[j])\n",
    "                    dfs(i+1)\n",
    "                    has_used[j]=0\n",
    "                    path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        '''\n",
    "        res = []\n",
    "        path = []\n",
    "        length = len(nums)\n",
    "        global tmp_length\n",
    "        tmp_length = 0\n",
    "        index_set = set()\n",
    "        nums = sorted(nums)\n",
    "        used = [0 for i in range(length)]\n",
    "        def func(nums,start=0):\n",
    "            global tmp_length\n",
    "            for i in range(length):\n",
    "                if not used[i]:\n",
    "                    if i > 0 and nums[i] == nums[i-1] and not used[i-1]:\n",
    "                        continue\n",
    "                    path.append(nums[i])\n",
    "                    tmp_length += 1\n",
    "                    if tmp_length == length:\n",
    "                        res.append([ii for ii in path])\n",
    "                    used[i] = 1\n",
    "                    func(nums,0)\n",
    "                    tmp_length -= 1\n",
    "                    used[i] = 0\n",
    "                    path.pop()\n",
    "        func(nums)\n",
    "        return res\n",
    "\n",
    "        '''\n",
    "        path = []\n",
    "        res = []\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return [nums]\n",
    "        used = [0 for i in range(length)]\n",
    "        global tmp_count\n",
    "        tmp_count = 0\n",
    "        nums = sorted(nums)\n",
    "        def func(nums):\n",
    "            global tmp_count\n",
    "            for i in range(length):\n",
    "                if not used[i]:\n",
    "                    if i > 0 and nums[i] == nums[i-1] and not used[i-1]:\n",
    "                        continue\n",
    "                    path.append(nums[i])\n",
    "                    tmp_count += 1\n",
    "                    used[i] = 1\n",
    "                    if tmp_count == length:\n",
    "                        res.append([i for i in path])\n",
    "                        # continue\n",
    "                    func(nums)\n",
    "                    path.pop()\n",
    "                    used[i] = 0\n",
    "                    tmp_count -= 1\n",
    "        func(nums)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res, loc = [], {}\n",
    "        for num in nums:loc[num] = loc.get(num, 0)+1\n",
    "        keys = loc.keys()\n",
    "        def dfs(ans:List[int], step:int)->None:\n",
    "            if step == len(nums):\n",
    "                res.append(ans.copy())\n",
    "                return\n",
    "            for key in keys:\n",
    "                if loc[key]==0:continue\n",
    "                ans.append(key)\n",
    "                loc[key] -= 1\n",
    "                dfs(ans, step+1)\n",
    "                loc[key] += 1\n",
    "                ans.pop()\n",
    "        dfs([], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        def dfs(path,nums,used):\n",
    "            if path in res:\n",
    "                return\n",
    "            if len(path)==len(nums):\n",
    "                res.append(path[:])\n",
    "            for i in range(len(nums)):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                used[i]=True\n",
    "                path.append(nums[i])\n",
    "                dfs(path,nums,used)\n",
    "                path.pop()\n",
    "                used[i]=False\n",
    "        used=[False for _ in range(len(nums))]\n",
    "        dfs([],nums,used)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        visited = [False] * len(nums)\n",
    "        def backtrack(nums,visited):\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if i>0 and nums[i-1]==nums[i] and not visited[i-1]:\n",
    "                    continue\n",
    "                if not visited[i]:\n",
    "                    visited[i] = True\n",
    "                    path.append(nums[i])\n",
    "                    backtrack(nums,visited)\n",
    "                    path.pop()\n",
    "                    visited[i] = False\n",
    "        nums.sort()\n",
    "        backtrack(nums,visited)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        path = []\n",
    "        mark = [0 for i in range(n)]\n",
    "\n",
    "        def dfs():\n",
    "            if len(path) == n:\n",
    "                if path not in res:\n",
    "                    res.append(path[:])\n",
    "                return \n",
    "            for i in range(n):\n",
    "                if mark[i] == 0:\n",
    "                    path.append(nums[i])\n",
    "                    mark[i] = 1\n",
    "                    dfs()\n",
    "                    mark[i] = 0\n",
    "                    path.pop()\n",
    "\n",
    "\n",
    "        dfs()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        def backtrack(nums, path):\n",
    "            if not nums:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i - 1] == nums[i]: continue\n",
    "                path.append(nums[i])\n",
    "                backtrack(nums[:i] + nums[i+1:], path)\n",
    "                path.pop()\n",
    "\n",
    "        backtrack(nums, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        vis = [0]*n\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        def generate(cur):\n",
    "            if len(cur) == n:\n",
    "                ans.append(cur)\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if vis[j] or (j and nums[j] == nums[j-1] and not vis[j-1]): continue\n",
    "                vis[j] = 1\n",
    "                generate(cur+[nums[j]])\n",
    "                vis[j] = 0\n",
    "\n",
    "        generate([])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        path = []\n",
    "        reslist = []\n",
    "        used = [False] * len(nums)\n",
    "\n",
    "\n",
    "        def backtracking():\n",
    "            \n",
    "            if len(path) == len(nums):\n",
    "                reslist.append(path[:])\n",
    "\n",
    "            layer_dict = {}\n",
    "            for i in range(len(nums)):\n",
    "                if used[i] == True or nums[i] in layer_dict:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = True\n",
    "                layer_dict[nums[i]] = 1\n",
    "                backtracking()\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "            return\n",
    "        \n",
    "        backtracking()\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res, n = [], len(nums)\n",
    "        visited = [False for _ in range(n)]\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        def dfs(path):\n",
    "            if len(path) == n:\n",
    "                res.append([nums[i] for i in path])\n",
    "            \n",
    "            for i in range(n):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                \n",
    "                if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:\n",
    "                    continue\n",
    "                \n",
    "                visited[i] = True\n",
    "                dfs(path + [i])\n",
    "                visited[i] = False\n",
    "\n",
    "        dfs([])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = []\n",
    "        ln = len(nums)\n",
    "        def backtracking(pos: int):\n",
    "            if pos == ln:\n",
    "                result.append(nums[:])\n",
    "                return\n",
    "            # 当前位置元素选谁？\n",
    "            visited = set()\n",
    "            for i in range(pos, ln):\n",
    "                if nums[i] in visited:\n",
    "                    continue\n",
    "                visited.add(nums[i])\n",
    "                nums[pos], nums[i] = nums[i], nums[pos]\n",
    "                backtracking(pos + 1)\n",
    "                nums[pos], nums[i] = nums[i], nums[pos]\n",
    "            \n",
    "        backtracking(0)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        l = []\n",
    "        Len = len(nums)\n",
    "        PosNextValue, PosUse = defaultdict(set), dict()\n",
    "        \n",
    "        def Find(n, pre):\n",
    "            if n == Len:\n",
    "                ans.append(l.copy())\n",
    "                return\n",
    "            for i in range(Len):\n",
    "                if PosUse.get(i, -1) == -1:\n",
    "                    if nums[i] not in PosNextValue[pre]:\n",
    "                        PosNextValue[pre].add(nums[i])\n",
    "                        PosUse[i] = 1\n",
    "                        l.append(nums[i])\n",
    "                        Find(n + 1, i)\n",
    "                        l.pop()\n",
    "                        PosUse[i] = -1\n",
    "            PosNextValue[pre].clear()\n",
    "        Find(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        path = [0] * n\n",
    "        onPath = [False] * n\n",
    "\n",
    "        def dfs(i):\n",
    "\n",
    "            if i == n:\n",
    "                if path not in ans:\n",
    "                    ans.append(path.copy())\n",
    "                return\n",
    "            \n",
    "            for j in range(n):\n",
    "                if not onPath[j]:\n",
    "                    path[i] = nums[j]\n",
    "                    onPath[j] = True\n",
    "                    dfs(i+1)\n",
    "\n",
    "                    onPath[j] = False\n",
    "            \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        vis = [False]*n\n",
    "        res = set()\n",
    "        path = []\n",
    "        def dfs(s):\n",
    "            if s == len(nums):\n",
    "                res.add(tuple(path[:]))\n",
    "            for i in range(n):\n",
    "                if vis[i] == False:\n",
    "                    path.append(nums[i])\n",
    "                    vis[i] = True\n",
    "                    dfs(s+1)\n",
    "                    vis[i] = False\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        res1 = sorted([list(i) for i in res])\n",
    "        return res1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        info = {}\n",
    "        for num in nums:\n",
    "            info[num] = info.get(num, 0) + 1\n",
    "        result = []\n",
    "        \n",
    "        def dfs(temp):\n",
    "            temp = temp[::]\n",
    "            if len(temp) == len(nums):\n",
    "                result.append(temp)\n",
    "                return\n",
    "            for num in info:\n",
    "                if info[num]:\n",
    "                    info[num] -= 1\n",
    "                    temp.append(num)\n",
    "                    dfs(temp)\n",
    "                    temp.pop(-1)\n",
    "                    info[num] += 1\n",
    "        \n",
    "        dfs([])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        path = []\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        def backtracking(start, nums):\n",
    "            # 终止条件\n",
    "            if start == n and path.copy() not in ans:\n",
    "                ans.append(path.copy())\n",
    "            \n",
    "            # 循环递归\n",
    "            for num in nums:\n",
    "                path.append(num)\n",
    "                idx = nums.index(num)\n",
    "                nums.pop(idx)\n",
    "                backtracking(start + 1, nums)\n",
    "                nums.insert(idx, num)\n",
    "                path.pop()\n",
    "        \n",
    "        backtracking(0, nums)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        def dfs(mark=0):\n",
    "            if mark == n-1:\n",
    "                res.append(nums[:])\n",
    "                return \n",
    "            vis = set()\n",
    "            for i in range(mark, n):\n",
    "                if nums[i] in vis: continue\n",
    "                vis.add(nums[i])\n",
    "                nums[i], nums[mark] = nums[mark], nums[i]\n",
    "                dfs(mark+1)\n",
    "                nums[i], nums[mark] = nums[mark], nums[i]\n",
    "        \n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        dfs()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        labeled_set = set()\n",
    "        ans_set = set()\n",
    "\n",
    "        def recursion (cur_idx, temp_list):\n",
    "            labeled_set.add(cur_idx)\n",
    "            temp_list.append(nums[cur_idx])\n",
    "            if len(temp_list) == len(nums):\n",
    "                if tuple(temp_list) not in ans_set:\n",
    "                    ans_set.add(tuple(temp_list))\n",
    "            \n",
    "            for next_idx in range(len(nums)):\n",
    "                if next_idx not in labeled_set:\n",
    "                    recursion(next_idx, temp_list)\n",
    "            \n",
    "            labeled_set.remove(cur_idx)\n",
    "            temp_list.pop()\n",
    "            return\n",
    "        \n",
    "        for index in range(len(nums)):\n",
    "            recursion(index, [])\n",
    "        \n",
    "        return list(ans_set)\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        vist = [False] * n\n",
    "        temp = []\n",
    "        ans = []\n",
    "\n",
    "        def dfs():\n",
    "            if len(temp) == n:\n",
    "                ans.append(temp.copy())\n",
    "                return\n",
    "            for index, num in enumerate(nums):\n",
    "                if vist[index] or (index > 0 and num == nums[index-1] and not vist[index-1]):\n",
    "                    continue\n",
    "                vist[index] = True\n",
    "                temp.append(num)\n",
    "                dfs()\n",
    "                temp.pop()\n",
    "                vist[index] = False\n",
    "        dfs()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        path = []\n",
    "        used = [False] * len(nums)\n",
    "        def backtrack(nums):\n",
    "            nonlocal res, path, used\n",
    "            if len(path) > len(nums):\n",
    "                return\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if used[i] == True:\n",
    "                    continue\n",
    "                if i > 0 and nums[i] == nums[i-1] and used[i-1] == False:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = True\n",
    "                backtrack(nums)\n",
    "                used[i] = False\n",
    "                path.pop()\n",
    "        backtrack(nums)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
